/*      Torneo Interuniversitario de Programacion
 *      Problema C
 *      Circuitos Turísticos
 *                                              */

#include <stdio.h>
#include <stdlib.h>

void preparar_matrix(int nodos, int **matrix);
void imprimir_matrix(int nodos, int **matrix);
void obtener_grados(int nodos, int *grados, int **matrix);
void calcular_rutas(int *grados, int **matrix);

int main()
{
        int i, nodos = 0, rutas = nodos + 1, dest_a, dest_b;
        int gr0 = 0, gr1 = 0, puentes = 0;

        while ((nodos != -1) && (rutas != -1)) {
                scanf("%d %d", &nodos, &rutas);
                fprintf(stderr, "\nIngresado %d nodos. Esperando %d rutas:\n",
                        nodos, rutas);

                /* Reservo memoria */
                int **matrix = (int **)malloc(nodos * sizeof(int *));
                int *grados = (int *)malloc(nodos * sizeof(int));

                for (i = 0; i < nodos; i++)
                        matrix[i] = (int *)malloc(nodos * sizeof(int));

                /* Lleno la diagonal ppal y pongo a 0 lo demás */
                preparar_matrix(nodos, matrix);

                /* Pongo un 1 en la matriz donde los destinos están ligados */
                for (i = 0; i < rutas; i++) {
                        scanf("%d %d", &dest_a, &dest_b);
                        matrix[dest_a - 1][dest_b - 1] = 1;
                        matrix[dest_b - 1][dest_a - 1] = 1;
                }

                obtener_grados(nodos, grados, matrix);

                for (i=0;i<nodos;i++)
                	fprintf(stderr,"%d ", grados[i]);
                fprintf(stderr, "\n");

                for (i=0; i<nodos; i++){
                	if (grados[i]==0)
                		gr0++;
                	else if (grados[i]==1)
                		gr1++;
                }

                puentes = 0;
                fprintf(stderr,"Grado 0: %d\n", gr0);
                fprintf(stderr,"Grado 1: %d\n", gr1);

                if (gr0 >= 2)
                	puentes = gr0 - 1;

                if (( (gr1 % 2) == 0 ) && (gr1 > 0) )
                	puentes += gr1/2 +1;
                else
                	puentes += gr1/2 + 2;

                //fprintf(stderr,"N° de puentes: ");
                printf("%d\n", puentes);




                calcular_rutas(grados, matrix);

                /*      Acá iría el algoritmo   */
                /*                              */

                /* Imprimo la matriz para ver lo que acabé de poner */
                imprimir_matrix(nodos, matrix);

                gr0 = gr1 = 0;
                free(grados);
                free(matrix);
        }

        return EXIT_SUCCESS;
}

void preparar_matrix(int nodos, int **matrix)
{
        int i, j;

        for (i = 0; i < nodos; i++)
                for (j = 0; j < nodos; j++) {
                        matrix[i][j] = 0;
                        if (j == i)
                                matrix[i][j] = 0;
                }

}

void imprimir_matrix(int nodos, int **matrix)
{
        int i, j;

        for (i = 0; i < nodos; i++)
                for (j = 0; j < nodos; j++) {
                        fprintf(stderr, "  %i", matrix[i][j]);
                        if (j == (nodos - 1))
                                fprintf(stderr, "\n");
                }

}

void obtener_grados(int nodos, int *grados, int **matrix)
{
        int i, j;

        for (i = 0; i < nodos; i++)
                grados[i]=0;

        for (i = 0; i < nodos; i++)
                for (j = 0; j < nodos; j++)
                        if (matrix[i][j] != 0)
                            grados[i]++;
    return;
}

void calcular_rutas(int *grados, int **matrix)
{
    /** TODO **/

}

